Quantifying the proximity, relevance and/or similarity between two vertices, and more generally, finding the k nearest neighbors (k-nns) of a given vertex in a large, time-evolving graph, is a fundamental building block for many applications. For example, in social networking graphs where the vertices are users and the edges represent connections between them, it may be desirable to recognize “nearby” but currently unconnected users, and recommend them to a particular user. In customer-product graphs, it may be desirable to recommend products to a customer based on a profile such as purchases and search history of “nearby” customers.
Existing approaches suffer from drawbacks such as, for example, not being scalable because they assume that the entire graph resides in the memory. Some existing approaches only work on static graphs, and other approaches work only on special types of time-varying graphs.